package com.ryujung.sort;

import java.util.Arrays;

public class CountingSort {

    /**
     * 计数排序
     * 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
     * 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
     * 
     * 当前算法仅可排序0 ~ Integer.MAX_VALUE (2^31 - 1) 范围的整数
     * 
     */
    public static void countingSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = Math.max(max, i);
        }
        int[] countArr = new int[max + 1];
        for (int i : arr) {
            countArr[i]++;
        }
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 2, 1 };
        int[] arr1 = { 5, 3, 8, 6, 4 };
        int[] arr2 = { 3, 1, 4, 2, 5 };
        int[] arr3 = { 9, 7, 6, 2, 4, 3, 1, 5, 8 };

        countingSort(arr);
        System.out.println(Arrays.toString(arr));
        countingSort(arr1);
        System.out.println(Arrays.toString(arr1));
        countingSort(arr2);
        System.out.println(Arrays.toString(arr2));
        countingSort(arr3);
        System.out.println(Arrays.toString(arr3));
    }
}
